//链表得中间结点
//快慢指针
//给你单链表的头结点 head ，请你找出并返回链表的中间结点。
//如果有两个中间结点，则返回第二个中间结点。


#include<stdio.h>
#include<stdlib.h>


struct ListNode
{
	int val;
	struct ListNode* next;
};

void SLTNodePrintf(struct ListNode* ps)
{
	struct ListNode* cur = ps;
	while (cur)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}

struct ListNode* middleNode(struct ListNode* head)
{
	struct ListNode* slow = head;
	struct ListNode* fast = head;
	//fast指针 一次走两步  slow一次走一步
	while ((fast!=NULL) && (fast->next!=NULL))
	{
		fast = fast->next->next;
		slow = slow->next;
	}
	return slow;
}



int main()
{
	struct ListNode* n1 = malloc(sizeof(struct ListNode));
	struct ListNode* n2 = malloc(sizeof(struct ListNode));
	struct ListNode* n3 = malloc(sizeof(struct ListNode));
	struct ListNode* n4 = malloc(sizeof(struct ListNode));

	n1->val = 1;
	n2->val = 2;
	n3->val = 3;
	n4->val = 4;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;
	SLTNodePrintf(n1);

	struct ListNode* newnode = middleNode(n1);
	SLTNodePrintf(newnode);

	return 0;
}